package com.javaDemo.ti;

import com.javaDemo.node.TreeNode;
import java.util.HashMap;

/**
 * 二叉树构建器
 * 
 * @author csy
 * @date 2021/6/1 11:09
 * @description 根据前序遍历和中序遍历序列构建二叉树
 * 
 *              解题思路：
 *              1. 前序遍历的第一个节点是根节点
 *              2. 在中序遍历中找到根节点的位置，可将数组分为左右子树
 *              3. 递归构建左右子树
 *              4. 使用HashMap存储中序遍历的值和索引映射，优化查找效率
 * 
 *              时间复杂度：O(n)，其中n为节点数量
 *              空间复杂度：O(n)，主要是哈希表的开销
 */
public class BinaryTreeBuilder {
    // 存储中序遍历的值到索引的映射，用于O(1)时间内找到根节点位置
    private HashMap<Integer, Integer> inorderValueToIndex;

    /**
     * 构建二叉树的主方法
     *
     * @param preorder 前序遍历序列
     * @param inorder  中序遍历序列
     * @return 构建好的二叉树的根节点
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        // 初始化哈希映射
        inorderValueToIndex = new HashMap<>();
        for (int i = 0; i < n; i++) {
            inorderValueToIndex.put(inorder[i], i);
        }
        return buildTreeHelper(preorder, inorder, 0, n - 1, 0, n - 1);
    }

    /**
     * 递归构建二叉树的辅助方法
     *
     * @param preorder 前序遍历序列
     * @param inorder  中序遍历序列
     * @param preStart 当前前序遍历的起始位置
     * @param preEnd   当前前序遍历的结束位置
     * @param inStart  当前中序遍历的起始位置
     * @param inEnd    当前中序遍历的结束位置
     * @return 当前子树的根节点
     */
    private TreeNode buildTreeHelper(int[] preorder, int[] inorder,
            int preStart, int preEnd, int inStart, int inEnd) {
        // 递归终止条件
        if (preStart > preEnd) {
            return null;
        }

        // 前序遍历的第一个节点是根节点
        int rootValue = preorder[preStart];
        TreeNode root = new TreeNode(rootValue);

        // 在中序遍历中找到根节点的位置
        int rootIndex = inorderValueToIndex.get(rootValue);

        // 计算左子树的节点数量
        int leftSubtreeSize = rootIndex - inStart;

        // 递归构建左子树
        root.left = buildTreeHelper(
                preorder, inorder,
                preStart + 1, // 左子树的前序遍历起始位置
                preStart + leftSubtreeSize, // 左子树的前序遍历结束位置
                inStart, // 左子树的中序遍历起始位置
                rootIndex - 1 // 左子树的中序遍历结束位置
        );

        // 递归构建右子树
        root.right = buildTreeHelper(
                preorder, inorder,
                preStart + leftSubtreeSize + 1, // 右子树的前序遍历起始位置
                preEnd, // 右子树的前序遍历结束位置
                rootIndex + 1, // 右子树的中序遍历起始位置
                inEnd // 右子树的中序遍历结束位置
        );

        return root;
    }
}